/*
 * @lc app=leetcode.cn id=654 lang=cpp
 *
 * [654] 最大二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode *constructMaximumBinaryTree(vector<int> &nums)
    {
        //最大二叉树 根节点是最大的值 左子树是最大值左边的最大二叉树 右子树同理
        if (nums.size() == 0)
        {
            return NULL;
        }
        return traval(nums, 0, nums.size());
    }
    TreeNode *traval(vector<int> &nums, int begin, int end)
    {
        //第一步 区间左闭右开
        if (begin == end)
        {
            //都为空
            return NULL;
        }
        //第二步 寻找当前最大值
        int maxval = INT32_MIN;
        int mysplit; //记录最大值所在位置
        for (int i = begin; i < end; i++)
        {
            if (maxval < nums[i])
            {
                maxval = nums[i];
                mysplit = i;
            }
        }
        TreeNode *node = new TreeNode(maxval);
        //如果当前为叶节点 直接返回节点
        if (end - begin == 1)
        {
            return node;
        }

        //第三步 分割数组 左闭右开
        int leftbegin = begin;
        int leftend = mysplit;

        int rightbegin = mysplit + 1;
        int rightend = end;

        //第四步 递归求解
        node->left = traval(nums, leftbegin, leftend);
        node->right = traval(nums, rightbegin, rightend);

        return node;
    }
};
// @lc code=end
